package offer.diff;

/**
 * https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?tpId=13&tqId=11183&tPage=1&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&from=cyc_github&tab=answerKey
 * @author DengYuan2
 * @create 2021-03-18 18:44
 */
public class n_42 {
    public static void main(String[] args) {
        int[] arr={6, -3, -2, 7, -15, 1, 2, 2};
        n_42 n = new n_42();
        int ret = n.FindGreatestSumOfSubArray(arr);
        System.out.println(ret);
    }

    /**
     * 动态规划
     * 思路：F(i)为以第i个元素为末尾的子数组的最大和，则F(i)=max(F(i-1)+array[i],array[i])
     * res为全部中的最大值
     * @param array
     * @return
     */
    public int FindGreatestSumOfSubArray(int[] array) {
        int res=Integer.MIN_VALUE;
        int sum=array[0];
        for (int i = 1; i < array.length; i++) {
            sum=Math.max(sum+array[i],array[i]);
            res=Math.max(sum,res);
        }
        return res;
    }

}
